The X-Philes (2nd Revision)/The X-Philes Number 1 (1995).iso/xphiles/hp48_2/obj.pos

Text File | 1995-03-23 | 7KB | 162 lines

Article 1853 of comp.sys.handhelds:
Path: en.ecn.purdue.edu!pur-ee!mentor.cc.purdue.edu!purdue!tut.cis.ohio-state.edu!snorkelwacker!usc!elroy.jpl.nasa.gov!jarthur!nntp-server.caltech.edu!piglet!madler
From: [e-mail] (Mark Adler)
Newsgroups: comp.sys.handhelds
Subject: Re: My last post on sorting (sure) for the HP-48SX
Message-ID: <[e-mail]>
Date: 16 Apr 90 19:49:58 GMT
References: <[e-mail]> <[e-mail]>
Sender: [e-mail]
Organization: California Institute of Technology, Pasadena
Lines: 147


Oops on OPOS.  Here is a corrected version of OPOS---the last one
didn't work for elements that belonged on the end of the list.

Also included here is an improved QPART using Alonzo's code for
swapping [i] and [j] more efficiently.  (I see that Alonzo can't
resist small tweaks either.)

Mark Adler
[e-mail]


%%HP: T(3)A(R)F(.);
@ OPOS crc #DEh length 142
@
@ by Mark Adler  16 Apr 1990
@
@ Ordered POS: the arguments are a list in level 2 and the element to
@ locate in level 1.  The result is the location in level 2 and a
@ boolean in level 1 which is true if the element is in the list.  The
@ location has the range 1..n+1, where n is the number of entries in
@ the list.  n+1 indicates the element belongs at the end of the list
@ (the boolean is always false in this case).  It is assumed that the
@ input list is ordered so that the first entry is less than or equal
@ to the second entry, the second is less than or equal to the third,
@ etc.
@
@ OPOS uses SRCH to find where in the list the element goes.  SRCH
@ uses the ">" operation to compare elements, but this can be changed
@ in SRCH---see the comments in SRCH.  The ">" in this routine would
@ also have to be changed in the same way.
@
\<<
  SWAP OBJ\-> \-> n
  \<<
    n 1 + ROLL n SRCH                   @ do search
    3 - \-> k j                         @ save k, index
    \<<
      IF j DUP THEN                     @ if j not past end,
        PICK k > NOT                    @  see if k in list
      END
      n 1 + ROLLD n DROPN               @ trash list
      n j - 1 +                         @ compute location
      SWAP                              @ return index, boolean
    \>>
  \>>
\>>


%%HP: T(3)A(R)F(.);
@ QPART crc #156h length 412
@
@ by Mark Adler  16 Apr 1990
@
@ Given a partition of the stack, pick an entry in the partition and
@ split the partition into two partitions such that all the entries in
@ the first one are less than the entry picked, and all the entries in
@ the second one are greater than the entry picked, and the entry is
@ placed between them.  Then call this routine recursively for each of
@ those partitions, unless the partition is 20 entries or less.  A
@ final pass of an insertion sort should be done to sort the remaining
@ short partitions.  The value of 20 was determined experimentally on
@ test cases of lists of random reals.
@
@ The entry for partitioning is picked using the median method, which
@ picks the median value of the entries at the beginning, middle, and
@ end of the list.  This makes the sort fast for already sorted lists,
@ and greatly reduces the probability of the sort taking order n^2
@ time.  It also reduces the total number of comparisons, speeding the
@ sort somewhat.  Most importantly, an additional step of sorting the
@ first and last elements of the list (which adds one compare) allows
@ the inner loops of the algorithm to not have to check for the bounds
@ of the partition.  This special-purpose three element sort does not
@ cost extra, since the outer two elements would have to have been
@ compared and swapped anyway if they were in the wrong place.  Thanks
@ to Alonzo Gariepy for an improved swap of [i] and [j].
@
@ The arguments to QPART are two integers specifying the stack levels
@ to partition.  The arguments refer to the stack after the arguments
@ are removed from the stack.  The integer in the first level minus 1
@ is the starting level, and the integer in level 2 is the ending level
@ to partition.  So, for example, to partition the stack levels 1
@ through n, the calling sequence would be "n 2 QPART".  Since QPART
@ does not check the partition size on entry, the calling routine
@ should do that and avoid calling QPART for sizes of 20 or less.
@
@ The algorithm can be modified to sort objects besides reals and
@ strings by replacing the ">" in the "IF DUP2 >"'s and in the "PICK >"
@ and replacing the "<" in the "PICK <" with the appropriate code for
@ the object.  The routine can be generalized (at a speed penalty) by
@ replacing said ">"'s with "GT" and the said "<" with "SWAP GT" and
@ defining a function "GT" that does the job before doing the sort.
@
\<<
  @ sort the partition of the stack from level l-1 to level r (after
  @  l and r are pulled off of the stack).
  \-> r l \<<
    @
    @ sort [l-1], [m], [r] so that [l-1] >= [m] >= [r] where m points
    @  to the middle of the partition.
    @
    r l + 2 / FLOOR ROLL                @ get [m]
    l ROLL                              @ get [l-1]
    IF DUP2 > THEN SWAP END             @ sort [m], [l-1]
    l ROLLD r ROLL                      @ put back new [l-1]; get [r]
    IF DUP2 > THEN                      @ if [r], [m] sorted,
      r                                 @  then just put [r] back
    ELSE
      SWAP r ROLLD l ROLL               @ else sort [r], [m]; get [l-1]
      IF DUP2 > THEN SWAP END           @  and re-sort [m] and [l-1]
      l                                 @ put [l-1] back
    END
    ROLLD
    @
    @ start sorting inside [l-1], [r] since [l-1] and [r] are already
    @ sorted.  put [m] in list so that [i] >= [m] >= [j] for i < j.
    @
    r 3 + SWAP                          @ i = l-1 (loop begins "1 +")
    l 3 +                               @ j = r-1 (since m pulled out)
    WHILE                               @ stack is i+4,[m],j+4,list...
      WHILE 1 + DUP2 PICK < REPEAT END  @ now [m] >= [i]
      SWAP ROT
      WHILE 1 - DUP2 PICK > REPEAT END  @ now [j] >= [m]
      ROT DUP2 >                        @ until j <= i
    REPEAT                              @ stack is i+4,j+4,[m],list...
      DUP2 SWAP ROLL SWAP ROLLD         @ swap [i] and [j]
      DUP2 ROLL OVER ROLLD
      DROP ROT SWAP                     @ stack is i+4,[m],j+4,list...
    END
    DROP 2 - SWAP OVER ROLLD            @ put [m] after [j]
    @
    @ sort the partitions [j+2..r] and [l-1..j] by calling this program
    @  recursively, but only if the partition has length > 20.  The
    @  stack is j+2,list...
    @
    IF r DUP2 - -18 < THEN              @ check top partition
      SWAP DUP 'r' STO 1 + QPART r      @ save j+2 in r
    ELSE
      DROP
    END                                 @ j+2 left on stack
    IF 2 - l DUP2 - 18 > THEN           @ check bottom partition
      QPART
    ELSE
      DROP2
    END                                 @ leave the list on the stack
  \>>
\>>